A video communication system typically comprises a source encoding system, a channel and a source decoding system. Said source encoding system generates variable-length codeword sequences and transmits them through said channel to said source decoding system that decodes them by virtue of a shared code.
As there are some perturbations on the channel, a received codeword sequence contains errors; hence, there is a plurality of possible decoded codeword sequences.
The source decoder then acts as an estimator of the received sequence by selecting one of the possible decoded codeword sequences based on a best metric between all the metrics associated with these possible sequences. The computation of the best metric is usually called metric derivation. Such an estimation is usually based either on a Viterbi algorithm or on a stack algorithm, said stack algorithm being described in the reference “Buttigieg-Variable-length error-correcting codes—PhD thesis, University of Manchester, United Kingdom, 1995”.
One major problem of such an estimation is that said estimation requires a computation of the metric associated with each codeword in each decoding step. Hence, the best partially decoded codeword sequence is extended by all the codewords, i.e. all the metrics of all the codewords are calculated, then a new best-codeword at a considered time is chosen as a function of its metric and is extended again by all the codewords until a number of extended codewords is equal to a received codeword sequence length. This computation makes a metric derivation used in the Viterbi or stack algorithms the most costly part of decoding in terms of central processing unit (cpu) requirements.